//2021/5/18 每日一题 O(n2) 到 O(n)



// /**
//  * @param {number[]} arr
//  * @return {number}
//  */
//  var countTriplets = function(arr) {
//     let i = 1;
//     let n = arr.length;
//     let ret = 0;
//     while(i < n){
//         let left = new Map();
//         let right = new Map();
//         let s = 0;
//         for(let j=i-1;j>=0;j--){
//             s^=arr[j];
//             if(left.has(s)){
//                 left.set(s,left.get(s)+1);
//             }
//             else{
//                 left.set(s,1);
//             }
//         }
//         s=0;
//         for(let j=i;j<n;j++){
//             s^=arr[j];
//             if(right.has(s)){
//                 right.set(s,right.get(s)+1);
//             }
//             else{
//                 right.set(s,1);
//             }
//         }
//         for(let j of left.keys()){
//             ret+= right.has(j) ? left.get(j)*right.get(j):0;
//         }
//         i++;
//     }
//     return ret
// };

// 执行用时：
// 128 ms
// , 在所有 JavaScript 提交中击败了
// 33.33%
// 的用户
// 内存消耗：
// 44.1 MB
// , 在所有 JavaScript 提交中击败了
// 6.67%
// 的用户

/**
 * @param {number[]} arr
 * @return {number}
 */
 var countTriplets = function(arr) {
    let ret=0;
    let prefix=new Map();
    let sum=new Map();
    prefix.set(0,1);
    sum.set(0,-1);
    let s=0;
    for (let [index,i] of arr.entries()){
        s^=i;
        if(prefix.has(s)){
            ret+=(index-1)*prefix.get(s)-sum.get(s);
        }
        prefix.set(s, prefix.has(s) ? prefix.get(s)+1:1);
        sum.set(s, sum.has(s) ? sum.get(s)+index:index);
    }
    return ret;
};

console.log(countTriplets([7,11,12,9,5,2,7,17,22]))

// 执行用时：
// 100 ms
// , 在所有 JavaScript 提交中击败了
// 63.33%
// 的用户
// 内存消耗：
// 40.6 MB
// , 在所有 JavaScript 提交中击败了
// 10.00%
// 的用户